// Created by WXX on 2021/9/13 9:35
#include <iostream>
#include <vector>

using namespace std;

/**
 * 执行用时：8 ms, 在所有 C++ 提交中击败了80.25%的用户
 * 内存消耗：13.9 MB, 在所有 C++ 提交中击败了27.99%的用户
 */
class Solution {
public:

    vector<vector<int>> g;
    int n, m;
    vector<vector<bool>> st;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        g = image;
        n = g.size(), m = g[0].size();
        // st = vector<vector<bool>>(n, vector<bool>(m));
        st.resize(n, vector<bool>(m));  // 上面的写法也可以
        dfs(sr, sc);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (st[i][j])
                    g[i][j] = newColor;
        return g;
    }

    void dfs(int x, int y) {
        st[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (st[a][b]) continue;
            if (g[a][b] != g[x][y]) continue;
            dfs(a, b);
        }
    }
};

void OutputBasicArray2D(vector<vector<int>> nums) {

    cout << "[";
    for (int i = 0; i < nums.size(); i++) {
        if (i > 0 && i < nums.size()) cout << ' ';
        cout << "[";
        for (int j = 0; j < nums[i].size(); j++) {
            cout << nums[i][j];
            if (j != nums[i].size() - 1) cout << ", ";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ", " << endl;
    }
    cout << "]" << endl;
}

int main() {

    vector<vector<int>> image = {
            {1, 1, 1},
            {1, 1, 0},
            {1, 0, 1},
    };
    OutputBasicArray2D(Solution().floodFill(image, 1, 1, 2));

    return 0;
}
